1306. Сортировка ДНК

Одной из мер “неупорядоченности” в последовательности является количество пар элементов, которые находятся в неправильном порядке по отношению друг к другу. Например, в последовательности букв "DAABEC", эта мера равна 5, так как D больше четырех букв справа, а Е больше одной буквы справа. Этой мерой является количество инверсий в последовательности. Последовательность “AACEDGG” имеет только одну инверсию (E и D) – она почти отсортированная, в то время как последовательность “ZWQM” имеет 6 инверсий (она полностью неотсортированная).

Вам следует отсортировать последовательность ДНК строк (они содержат только четыре буквы A, C, G, Т). Однако сортировку следует производить не в алфавитном порядке, а в порядке “упорядоченности”, от “самых отсортированных” до “наименее отсортированных”. Все строки имеют одинаковую длину.

Вход. Первая строка содержит целое число M, за которым следует пустая строка и M тестов. Между соседними тестами находится пустая строка.

Первая строка каждого теста содержит два целых числа: натуральное число n (0 < n ≤ 50) – длина входных строк и натуральное число m (0 < m ≤ 100) – количество строк. Далее следуют m строк, каждая из которых имеет длину n.

Выход. Для каждого теста вывести последовательность строк в порядке от “наиболее отсортированной” до “наименее отсортированной”. Если две или более строки равны при указанной сортировке, то выводить их следует в том же порядке в каком они поступали на вход.

Между ответами на соседние тесты следует выводить пустую строку.

Пример входа	Пример выхода
1 10 6 AACATGAAGG TTTTGGCCAA TTTGGCCAAA GATCAGATTT CCCGGGGGGA ATCGATGCAT	CCCGGGGGGA AACATGAAGG GATCAGATTT ATCGATGCAT TTTTGGCCAA TTTGGCCAAA

РЕШЕНИЕ

сортировка

Анализ алгоритма

Для каждой строки вычислим число инверсий в ней. Это число вместе с самой строкой храним в векторе пар. Выполняем стабильную сортировку строк в порядке неубывания количества инверсий в них и выводим результат.

Реализация алгоритма

Строки вместе с количеством инверсий в них храним в векторе пар s.

vector<pair<string,int> > s;

Функция value вычисляет количество инверсий в строке s.

int value(string s)

{

int i, j, res = 0;

for(i = 0; i < n - 1; i++)

for(j = i + 1; j < n; j++)

if (s[i] > s[j]) res++;

return res;

}

Функция lt используется в стабильной сортировке строк.

int lt(pair<string,int> x, pair<string,int> y)

{

return (x.second < y.second);

}

Основной цикл программы. Читаем количество входных тестов tests.

scanf("%d",&tests);

while(tests--)

{

s.clear();

Для каждого теста читаем значения n и m. Для каждой строки вычисляем число инверсий в ней, заносим их структуру типа DNA и сохраняем в векторе s.

scanf("%d %d\n",&n,&m);

for(i = 0; i < m; i++)

{

gets(stroka);

s.push_back(make_pair(stroka,value(stroka)));

}

Проводим стабильную сортировку строк.

stable_sort(s.begin(),s.end(),lt);

Выводим результат. Между тестами выводим пустую строку.

for(iter = s.begin();iter != s.end();iter++)

puts((*iter).first.c_str());

if (tests) printf("\n");

}